#define  _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <unordered_map>
using namespace std;


class LRUCache {
public:

    struct ListNode
    {
        ListNode(pair<int, int> kv)
            :_kv(kv)
            , pre(nullptr)
            , next(nullptr)
        {}

        pair<int, int> _kv;
        ListNode* next;
        ListNode* pre;
    };


    LRUCache(int capacity)
    {
        _cap = capacity;
        head = new ListNode({ -1, -1 });
        tail = new ListNode({ -1, -1 });

        head->next = tail;
        tail->pre = head;
    }

    void removeToHead(ListNode* cur)
    {
        ListNode* save = head->next;

        cur->next = save;
        save->pre = cur;

        cur->pre = head;
        head->next = cur;
    }

    int deleteListNode()
    {
        ListNode* save = tail->pre->pre, * deleteNode = tail->pre;

        save->next = tail;
        tail->pre = save;

        int val = deleteNode->_kv.first;
        delete deleteNode;

        return val;
    }

    int get(int key)
    {
        if (um.find(key) == um.end())
            return -1;

        ListNode* cur = um[key];
        ListNode* preNode = cur->pre, * nextNode = cur->next;
        preNode->next = nextNode;
        nextNode->pre = preNode;

        removeToHead(um[key]);
        return um[key]->_kv.second;
    }

    void put(int key, int value)
    {
        if (um.find(key) != um.end())
        {
            um[key]->_kv.second = value;

            ListNode* cur = um[key];
            ListNode* preNode = cur->pre, * nextNode = cur->next;
            preNode->next = nextNode;
            nextNode->pre = preNode;

            removeToHead(um[key]);

            return;
        }

        if (um.size() == _cap)
        {
            int val = deleteListNode();
            um.erase(val);
        }

        ListNode* node = new ListNode({ key, value });
        removeToHead(node);
        um[key] = node;
    }

    ListNode* head;
    ListNode* tail;
    unordered_map<int, ListNode*> um;
    int _cap;
};


//int main()
//{
//    LRUCache A(2);
//   
//    cout << A.get(2) << endl;
//    A.put(2, 6);
//    cout << A.get(1) << endl;
//    A.put(1, 5);
//
//    A.put(1, 2);
//    cout << A.get(1) << endl;
//    cout << A.get(2) << endl;
//
//    return 0;
//}